package main

import "fmt"

// 双100
func movingCount(m int, n int, k int) int {
	d := [4][2]int{[2]int{0, 1}, [2]int{0, -1}, [2]int{-1, 0}, [2]int{1, 0}}

	list := make([][]int, m)
	for i := range list {
		list[i] = make([]int, n)
	}

	// 得到位数和
	getDigitSum := func(num int) int {
		ans := 0
		for num > 0 {
			b := num % 10
			num = num / 10
			ans += b
		}
		return ans
	}
	dic := make(map[[2]int]bool)

	// 位置是否合格
	isValid := func(x, y int) bool {
		if x >= 0 && x < m && y >= 0 && y < n {
			return getDigitSum(x)+getDigitSum(y) <= k
		}
		return false
	}
	res := 0
	var helper func(x, y int)
	helper = func(x, y int) {
		if _, ok := dic[[2]int{x, y}]; !ok && isValid(x, y) {
			res++
			dic[[2]int{x, y}] = true
		} else {
			return
		}

		for _, value := range d {
			newX := x + value[0]
			newY := y + value[1]
			helper(newX, newY)

		}

	}
	helper(0, 0)
	return res
}

func main() {
	fmt.Println(movingCount(1, 2, 1))
}
